package com.yanceysong.codetop.s81_s90;

public class S88_Mid_152_乘积最大子数组 {

    /**
     * .S88_Mid_152_乘积最大子数组
     * .<p>
     * .<a href="https://leetcode.cn/problems/maximum-product-subarray/">...</a>
     * .<p>
     * .给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
     * .<p>
     * .测试用例的答案是一个 32-位 整数。
     * .<p>
     * .子数组 是数组的连续子序列。
     * .<p>
     * .示例 1：
     * .<p>
     * .输入：nums = [2,3,-2,4]
     * .输出：6
     * .解释：子数组 [2,3] 有最大乘积 6。
     * .<p>
     * .示例 2：
     * .<p>
     * .输入：nums = [-2,0,-1]
     * .输出：0
     * .解释：结果不能为 2, 因为 [-2,-1] 不是子数组。
     * .<p>
     * .提示：
     * .<p>
     * .1 <= nums.length <= 2 * .10^4
     * .-10 <= nums[i] <= 10
     * .nums 的任何前缀或后缀的乘积都 保证 是一个 32-位 整数
     * .<p>
     * .核心标签：动态规划、数组
     * .<p>
     * .解题思路：
     * .这是一个动态规划问题，但与最大和子数组不同，乘积问题需要特殊处理负数的情况。
     * .<p>
     * .关键难点：
     * .负数 × 负数 = 正数，所以当前的最小值（负数）乘以一个负数可能变成最大值
     * .<p>
     * .状态定义：
     * .maxProduct[i] 表示以 nums[i] 结尾的子数组的最大乘积
     * .minProduct[i] 表示以 nums[i] 结尾的子数组的最小乘积（可能是负数）
     * .<p>
     * .为什么需要维护最小值？
     * .因为当遇到负数时，之前的最小值（负数）乘以当前负数会变成最大值
     * .<p>
     * .状态转移方程：
     * .maxProduct[i] = max(nums[i], maxProduct[i-1] * nums[i], minProduct[i-1] * nums[i])
     * .minProduct[i] = min(nums[i], maxProduct[i-1] * nums[i], minProduct[i-1] * nums[i])
     * .<p>
     * .三种选择的含义：
     * .1. nums[i]：从当前位置重新开始（之前的乘积太小或遇到0）
     * .2. maxProduct[i-1] * nums[i]：延续之前的最大乘积
     * .3. minProduct[i-1] * nums[i]：之前的最小值（负数）乘以当前负数变成最大值
     * .<p>
     * .关键洞察：
     * .1. 必须同时维护最大值和最小值
     * .2. 负数会导致最大值和最小值互换
     * .3. 遇到0时，相当于重新开始
     * .4. 可以优化空间复杂度到 O(1)，只保存前一个状态
     * .<p>
     * .ASCII 图解示例 1：
     * .<p>
     * .输入：nums = [2, 3, -2, 4]
     * .<p>
     * .数组示意：
     * .<p>
     * .索引:     0    1    2    3
     * .        ┌───┬───┬───┬───┐
     * .值:     │ 2 │ 3 │-2 │ 4 │
     * .        └───┴───┴───┴───┘
     * .<p>
     * .动态规划过程：
     * .<p>
     * .初始化 (i=0)：
     * .maxProduct = 2
     * .minProduct = 2
     * .result = 2
     * .<p>
     * .i=1, nums[1]=3：
     * .候选值：
     * .  - nums[1] = 3
     * .  - maxProduct * nums[1] = 2 * 3 = 6
     * .  - minProduct * nums[1] = 2 * 3 = 6
     * .maxProduct = max(3, 6, 6) = 6  ✓
     * .minProduct = min(3, 6, 6) = 3
     * .result = max(2, 6) = 6
     * .<p>
     * .i=2, nums[2]=-2：
     * .候选值：
     * .  - nums[2] = -2
     * .  - maxProduct * nums[2] = 6 * (-2) = -12
     * .  - minProduct * nums[2] = 3 * (-2) = -6
     * .maxProduct = max(-2, -12, -6) = -2
     * .minProduct = min(-2, -12, -6) = -12  ✓ (保存最小负数)
     * .result = max(6, -2) = 6
     * .<p>
     * .i=3, nums[3]=4：
     * .候选值：
     * .  - nums[3] = 4
     * .  - maxProduct * nums[3] = -2 * 4 = -8
     * .  - minProduct * nums[3] = -12 * 4 = -48
     * .maxProduct = max(4, -8, -48) = 4
     * .minProduct = min(4, -8, -48) = -48
     * .result = max(6, 4) = 6  ✓ 最终答案
     * .<p>
     * .状态变化表：
     * .<p>
     * .i  | nums[i] | maxProduct | minProduct | result
     * .---|---------|------------|------------|--------
     * .0  |    2    |     2      |     2      |   2
     * .1  |    3    |     6      |     3      |   6
     * .2  |   -2    |    -2      |   -12      |   6
     * .3  |    4    |     4      |   -48      |   6  ✓
     * .<p>
     * .最大乘积子数组：[2, 3]，乘积 = 6
     * .<p>
     * .═══════════════════════════════════════════════════════════════
     * .<p>
     * .示例 2：nums = [-2, 0, -1]
     * .<p>
     * .数组示意：
     * .<p>
     * .索引:     0    1    2
     * .        ┌───┬───┬───┐
     * .值:     │-2 │ 0 │-1 │
     * .        └───┴───┴───┘
     * .<p>
     * .动态规划过程：
     * .<p>
     * .初始化 (i=0)：
     * .maxProduct = -2
     * .minProduct = -2
     * .result = -2
     * .<p>
     * .i=1, nums[1]=0：
     * .候选值：
     * .  - nums[1] = 0
     * .  - maxProduct * nums[1] = -2 * 0 = 0
     * .  - minProduct * nums[1] = -2 * 0 = 0
     * .maxProduct = max(0, 0, 0) = 0
     * .minProduct = min(0, 0, 0) = 0
     * .result = max(-2, 0) = 0  ✓
     * .<p>
     * .i=2, nums[2]=-1：
     * .候选值：
     * .  - nums[2] = -1
     * .  - maxProduct * nums[2] = 0 * (-1) = 0
     * .  - minProduct * nums[2] = 0 * (-1) = 0
     * .maxProduct = max(-1, 0, 0) = 0
     * .minProduct = min(-1, 0, 0) = -1
     * .result = max(0, 0) = 0  ✓ 最终答案
     * .<p>
     * .状态变化表：
     * .<p>
     * .i  | nums[i] | maxProduct | minProduct | result
     * .---|---------|------------|------------|--------
     * .0  |   -2    |    -2      |    -2      |  -2
     * .1  |    0    |     0      |     0      |   0
     * .2  |   -1    |     0      |    -1      |   0  ✓
     * .<p>
     * .最大乘积子数组：[0]，乘积 = 0
     * .<p>
     * .═══════════════════════════════════════════════════════════════
     * .<p>
     * .负数的影响示例：nums = [2, -5, -2, -4, 3]
     * .<p>
     * .数组示意：
     * .<p>
     * .索引:     0    1    2    3    4
     * .        ┌───┬───┬───┬───┬───┐
     * .值:     │ 2 │-5 │-2 │-4 │ 3 │
     * .        └───┴───┴───┴───┴───┘
     * .<p>
     * .关键观察：
     * .- [2, -5] = -10 (负数)
     * .- [2, -5, -2] = 20 (两个负数相乘变正数) ✓
     * .- [2, -5, -2, -4] = -80 (三个负数)
     * .- [-5, -2, -4, 3] = -120 (三个负数)
     * .- [-2, -4] = 8
     * .- [-2, -4, 3] = 24
     * .<p>
     * .动态规划过程：
     * .<p>
     * .i=0: max=2,   min=2,   result=2
     * .i=1: max=-5,  min=-10, result=2
     * .i=2: max=20,  min=-2,  result=20  ✓ (min=-10 * .-2 = 20)
     * .i=3: max=-4,  min=-80, result=20
     * .i=4: max=3,   min=-240, result=20
     * .<p>
     * .最大乘积子数组：[2, -5, -2]，乘积 = 20
     * .<p>
     * .这个例子展示了为什么需要维护最小值：
     * .当 i=2 时，minProduct=-10（负数）乘以 nums[2]=-2（负数）得到 20（正数）
     * .这个 20 成为了新的最大值！
     * .<p>
     * .═══════════════════════════════════════════════════════════════
     * .<p>
     * .包含0的情况：nums = [2, 3, 0, 4, 5]
     * .<p>
     * .数组示意：
     * .<p>
     * .索引:     0    1    2    3    4
     * .        ┌───┬───┬───┬───┬───┐
     * .值:     │ 2 │ 3 │ 0 │ 4 │ 5 │
     * .        └───┴───┴───┴───┴───┘
     * .<p>
     * .0 的作用：将数组分割成独立的部分
     * .- 左边部分：[2, 3]，最大乘积 = 6
     * .- 右边部分：[4, 5]，最大乘积 = 20
     * .<p>
     * .动态规划过程：
     * .<p>
     * .i=0: max=2,  min=2,  result=2
     * .i=1: max=6,  min=3,  result=6
     * .i=2: max=0,  min=0,  result=6  (遇到0，重置)
     * .i=3: max=4,  min=4,  result=6  (从4重新开始)
     * .i=4: max=20, min=5,  result=20  ✓
     * .<p>
     * .最大乘积子数组：[4, 5]，乘积 = 20
     * .<p>
     * .时间复杂度：O(n)
     * .- 只需遍历一次数组
     * .<p>
     * .空间复杂度：O(1)
     * .- 只使用了常量级别的额外空间（maxProduct, minProduct, result）
     */
    public int maxProduct(int[] nums) {
        // 边界条件检查
        if (nums == null || nums.length == 0) {
            return 0;
        }

        // 初始化：以第一个元素结尾的最大乘积和最小乘积
        int maxProduct = nums[0];  // 当前最大乘积
        int minProduct = nums[0];  // 当前最小乘积（可能是负数）
        int result = nums[0];      // 全局最大乘积

        int length = nums.length;

        // 从第二个元素开始遍历
        for (int i = 1; i < length; i++) {
            // 保存上一轮的最大值和最小值
            // 因为计算新的 maxProduct 时会用到旧的 maxProduct 和 minProduct
            int prevMax = maxProduct;
            int prevMin = minProduct;

            // 计算以当前元素结尾的最大乘积
            // 三个候选值：
            // 1. nums[i]：从当前位置重新开始
            // 2. prevMax * nums[i]：延续之前的最大乘积
            // 3. prevMin * nums[i]：之前的最小值（负数）乘以当前负数可能变成最大值
            maxProduct = Math.max(prevMax * nums[i], Math.max(nums[i], prevMin * nums[i]));

            // 计算以当前元素结尾的最小乘积
            // 同样三个候选值，取最小
            minProduct = Math.min(prevMin * nums[i], Math.min(nums[i], prevMax * nums[i]));

            // 更新全局最大乘积
            result = Math.max(maxProduct, result);
        }

        return result;
    }

    public int maxProductDP(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int n = nums.length;
        int[] dpMax = new int[n];
        int[] dpMin = new int[n];
        dpMax[0] = nums[0];
        dpMin[0] = nums[0];
        int result = nums[0];
        for (int i = 1; i < n; i++) {
            int a = nums[i];
            dpMax[i] = Math.max(a, Math.max(dpMax[i - 1] * a, dpMin[i - 1] * a));
            dpMin[i] = Math.min(a, Math.min(dpMax[i - 1] * a, dpMin[i - 1] * a));
            result = Math.max(result, dpMax[i]);
        }
        return result;
    }

    public static void main(String[] args) {
        S88_Mid_152_乘积最大子数组 solution = new S88_Mid_152_乘积最大子数组();

        System.out.println("=== 乘积最大子数组测试开始 ===");

        // 测试1: 示例1
        System.out.println("\n--- 测试1: 示例1 [2,3,-2,4] ---");
        testCase1(solution);

        // 测试2: 示例2
        System.out.println("\n--- 测试2: 示例2 [-2,0,-1] ---");
        testCase2(solution);

        // 测试3: 单个元素
        System.out.println("\n--- 测试3: 单个元素 [5] ---");
        testSingleElement(solution);

        // 测试4: 全是正数
        System.out.println("\n--- 测试4: 全是正数 [2,3,4] ---");
        testAllPositive(solution);

        // 测试5: 全是负数（偶数个）
        System.out.println("\n--- 测试5: 全是负数(偶数个) [-2,-3] ---");
        testAllNegativeEven(solution);

        // 测试6: 全是负数（奇数个）
        System.out.println("\n--- 测试6: 全是负数(奇数个) [-2,-3,-4] ---");
        testAllNegativeOdd(solution);

        // 测试7: 包含0
        System.out.println("\n--- 测试7: 包含0 [2,3,0,4,5] ---");
        testWithZero(solution);

        // 测试8: 负数变正数的情况
        System.out.println("\n--- 测试8: 负数变正数 [2,-5,-2,-4,3] ---");
        testNegativeToPositive(solution);

        // 测试9: 多个0
        System.out.println("\n--- 测试9: 多个0 [0,2,0] ---");
        testMultipleZeros(solution);

        // 测试10: 包含1和-1
        System.out.println("\n--- 测试10: 包含1和-1 [-1,-2,-3,-4] ---");
        testWithOnesAndNegativeOnes(solution);

        System.out.println("\n=== 所有测试完成 ===");
    }

    /**
     * .测试1: 示例1
     * .输入：[2,3,-2,4]
     * .期望输出：6
     */
    private static void testCase1(S88_Mid_152_乘积最大子数组 solution) {
        int[] nums = {2, 3, -2, 4};
        System.out.println("输入: [2, 3, -2, 4]");

        int result = solution.maxProduct(nums);

        System.out.println("输出: " + result);
        System.out.println("期望: 6");
        System.out.println("解释: 子数组 [2, 3] 有最大乘积 6");
        assert result == 6 : "结果应为 6";
        System.out.println("✓ 测试1通过");
    }

    /**
     * .测试2: 示例2
     * .输入：[-2,0,-1]
     * .期望输出：0
     */
    private static void testCase2(S88_Mid_152_乘积最大子数组 solution) {
        int[] nums = {-2, 0, -1};
        System.out.println("输入: [-2, 0, -1]");

        int result = solution.maxProduct(nums);

        System.out.println("输出: " + result);
        System.out.println("期望: 0");
        System.out.println("解释: 子数组 [0] 有最大乘积 0");
        assert result == 0 : "结果应为 0";
        System.out.println("✓ 测试2通过");
    }

    /**
     * .测试3: 单个元素
     * .输入：[5]
     * .期望输出：5
     */
    private static void testSingleElement(S88_Mid_152_乘积最大子数组 solution) {
        int[] nums = {5};
        System.out.println("输入: [5]");

        int result = solution.maxProduct(nums);

        System.out.println("输出: " + result);
        System.out.println("期望: 5");
        assert result == 5 : "单个元素应返回该元素";
        System.out.println("✓ 测试3通过");
    }

    /**
     * .测试4: 全是正数
     * .输入：[2,3,4]
     * .期望输出：24
     */
    private static void testAllPositive(S88_Mid_152_乘积最大子数组 solution) {
        int[] nums = {2, 3, 4};
        System.out.println("输入: [2, 3, 4]");

        int result = solution.maxProduct(nums);

        System.out.println("输出: " + result);
        System.out.println("期望: 24");
        System.out.println("解释: 全是正数，整个数组的乘积最大 = 2 * .3 * .4 = 24");
        assert result == 24 : "结果应为 24";
        System.out.println("✓ 测试4通过");
    }

    /**
     * .测试5: 全是负数（偶数个）
     * .输入：[-2,-3]
     * .期望输出：6
     */
    private static void testAllNegativeEven(S88_Mid_152_乘积最大子数组 solution) {
        int[] nums = {-2, -3};
        System.out.println("输入: [-2, -3]");

        int result = solution.maxProduct(nums);

        System.out.println("输出: " + result);
        System.out.println("期望: 6");
        System.out.println("解释: 偶数个负数相乘为正数 = -2 * .-3 = 6");
        assert result == 6 : "结果应为 6";
        System.out.println("✓ 测试5通过");
    }

    /**
     * .测试6: 全是负数（奇数个）
     * .输入：[-2,-3,-4]
     * .期望输出：12
     */
    private static void testAllNegativeOdd(S88_Mid_152_乘积最大子数组 solution) {
        int[] nums = {-2, -3, -4};
        System.out.println("输入: [-2, -3, -4]");

        int result = solution.maxProduct(nums);

        System.out.println("输出: " + result);
        System.out.println("期望: 12");
        System.out.println("解释: 奇数个负数，去掉一个负数，[-3, -4] = 12");
        assert result == 12 : "结果应为 12";
        System.out.println("✓ 测试6通过");
    }

    /**
     * .测试7: 包含0
     * .输入：[2,3,0,4,5]
     * .期望输出：20
     */
    private static void testWithZero(S88_Mid_152_乘积最大子数组 solution) {
        int[] nums = {2, 3, 0, 4, 5};
        System.out.println("输入: [2, 3, 0, 4, 5]");

        int result = solution.maxProduct(nums);

        System.out.println("输出: " + result);
        System.out.println("期望: 20");
        System.out.println("解释: 0将数组分割，右边 [4, 5] = 20 最大");
        assert result == 20 : "结果应为 20";
        System.out.println("✓ 测试7通过");
    }

    /**
     * .测试8: 负数变正数的情况
     * .输入：[2,-5,-2,-4,3]
     * .期望输出：20
     */
    private static void testNegativeToPositive(S88_Mid_152_乘积最大子数组 solution) {
        int[] nums = {2, -5, -2, -4, 3};
        System.out.println("输入: [2, -5, -2, -4, 3]");

        int result = solution.maxProduct(nums);

        System.out.println("输出: " + result);
        System.out.println("期望: 20");
        System.out.println("解释: 子数组 [2, -5, -2] = 2 * .(-5) * .(-2) = 20");
        assert result == 20 : "结果应为 20";
        System.out.println("✓ 测试8通过");
    }

    /**
     * .测试9: 多个0
     * .输入：[0,2,0]
     * .期望输出：2
     */
    private static void testMultipleZeros(S88_Mid_152_乘积最大子数组 solution) {
        int[] nums = {0, 2, 0};
        System.out.println("输入: [0, 2, 0]");

        int result = solution.maxProduct(nums);

        System.out.println("输出: " + result);
        System.out.println("期望: 2");
        System.out.println("解释: 子数组 [2] 有最大乘积 2");
        assert result == 2 : "结果应为 2";
        System.out.println("✓ 测试9通过");
    }

    /**
     * .测试10: 包含1和-1
     * .输入：[-1,-2,-3,-4]
     * .期望输出：24
     */
    private static void testWithOnesAndNegativeOnes(S88_Mid_152_乘积最大子数组 solution) {
        int[] nums = {-1, -2, -3, -4};
        System.out.println("输入: [-1, -2, -3, -4]");

        int result = solution.maxProduct(nums);

        System.out.println("输出: " + result);
        System.out.println("期望: 24");
        System.out.println("解释: 偶数个负数，整个数组 = (-1) * .(-2) * .(-3) * .(-4) = 24");
        assert result == 24 : "结果应为 24";
        System.out.println("✓ 测试10通过");
    }
}
